// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "cc/quads/draw_polygon.h"

#include <stddef.h>

#include <vector>

#include "base/memory/ptr_util.h"
#include "cc/output/bsp_compare_result.h"
#include "cc/quads/draw_quad.h"

namespace {
// This threshold controls how "thick" a plane is. If a point's distance is
// <= |split_threshold|, then it is considered on the plane for the purpose of
// polygon splitting.
static const float split_threshold = 0.05f;

static const float normalized_threshold = 0.001f;

void PointInterpolate(const gfx::Point3F& from,
    const gfx::Point3F& to,
    double delta,
    gfx::Point3F* out)
{
    out->SetPoint(from.x() + (to.x() - from.x()) * delta,
        from.y() + (to.y() - from.y()) * delta,
        from.z() + (to.z() - from.z()) * delta);
}
} // namespace

namespace cc {

DrawPolygon::DrawPolygon()
{
}

DrawPolygon::DrawPolygon(const DrawQuad* original,
    const std::vector<gfx::Point3F>& in_points,
    const gfx::Vector3dF& normal,
    int draw_order_index)
    : order_index_(draw_order_index)
    , original_ref_(original)
    , is_split_(true)
{
    for (size_t i = 0; i < in_points.size(); i++) {
        points_.push_back(in_points[i]);
    }
#if DCHECK_IS_ON()
    normal_ = normal;
    ConstructNormal();
    DCHECK_LE((normal_ - normal).Length(), normalized_threshold);
#endif
    normal_ = normal;
}

// This takes the original DrawQuad that this polygon should be based on,
// a visible content rect to make the 4 corner points from, and a transformation
// to move it and its normal into screen space.
DrawPolygon::DrawPolygon(const DrawQuad* original_ref,
    const gfx::RectF& visible_layer_rect,
    const gfx::Transform& transform,
    int draw_order_index)
    : normal_(0.0f, 0.0f, 1.0f)
    , order_index_(draw_order_index)
    , original_ref_(original_ref)
    , is_split_(false)
{
    gfx::Point3F points[6];
    int num_vertices_in_clipped_quad;
    gfx::QuadF send_quad(visible_layer_rect);

    // Doing this mapping here is very important, since we can't just transform
    // the points without clipping and not run into strange geometry issues when
    // crossing w = 0. At this point, in the constructor, we know that we're
    // working with a quad, so we can reuse the MathUtil::MapClippedQuad3d
    // function instead of writing a generic polygon version of it.
    MathUtil::MapClippedQuad3d(
        transform, send_quad, points, &num_vertices_in_clipped_quad);
    for (int i = 0; i < num_vertices_in_clipped_quad; i++) {
        points_.push_back(points[i]);
    }
    transform.TransformVector(&normal_);
    ConstructNormal();
}

DrawPolygon::~DrawPolygon()
{
}

std::unique_ptr<DrawPolygon> DrawPolygon::CreateCopy()
{
    std::unique_ptr<DrawPolygon> new_polygon(new DrawPolygon());
    new_polygon->order_index_ = order_index_;
    new_polygon->original_ref_ = original_ref_;
    new_polygon->points_.reserve(points_.size());
    new_polygon->points_ = points_;
    new_polygon->normal_.set_x(normal_.x());
    new_polygon->normal_.set_y(normal_.y());
    new_polygon->normal_.set_z(normal_.z());
    return new_polygon;
}

//
// If this were to be more generally used and expected to be applicable
// replacing this with Newell's algorithm (or an improvement thereof)
// would be preferable, but usually this is coming in from a rectangle
// that has been transformed to screen space and clipped.
// Averaging a few near diagonal cross products is pretty good in that case.
//
void DrawPolygon::ConstructNormal()
{
    gfx::Vector3dF new_normal(0.0f, 0.0f, 0.0f);
    int delta = points_.size() / 2;
    for (size_t i = 1; i + delta < points_.size(); i++) {
        new_normal += CrossProduct(points_[i] - points_[0], points_[i + delta] - points_[0]);
    }
    float normal_magnitude = new_normal.Length();
    // Here we constrain the new normal to point in the same sense as the old one.
    // This allows us to handle winding-reversing transforms better.
    if (gfx::DotProduct(normal_, new_normal) < 0.0) {
        normal_magnitude *= -1.0;
    }
    if (normal_magnitude != 0 && normal_magnitude != 1) {
        new_normal.Scale(1.0f / normal_magnitude);
    }
    normal_ = new_normal;
}

#if defined(OS_WIN)
//
// Allows the unittest to invoke this for the more general constructor.
//
void DrawPolygon::RecomputeNormalForTesting()
{
    ConstructNormal();
}
#endif

float DrawPolygon::SignedPointDistance(const gfx::Point3F& point) const
{
    return gfx::DotProduct(point - points_[0], normal_);
}

// This function is separate from ApplyTransform because it is often unnecessary
// to transform the normal with the rest of the polygon.
// When drawing these polygons, it is necessary to move them back into layer
// space before sending them to OpenGL, which requires using ApplyTransform,
// but normal information is no longer needed after sorting.
void DrawPolygon::ApplyTransformToNormal(const gfx::Transform& transform)
{
    // Now we use the inverse transpose of |transform| to transform the normal.
    gfx::Transform inverse_transform;
    bool inverted = transform.GetInverse(&inverse_transform);
    DCHECK(inverted);
    if (!inverted)
        return;
    inverse_transform.Transpose();

    gfx::Point3F new_normal(normal_.x(), normal_.y(), normal_.z());
    inverse_transform.TransformPoint(&new_normal);
    // Make sure our normal is still normalized.
    normal_ = gfx::Vector3dF(new_normal.x(), new_normal.y(), new_normal.z());
    float normal_magnitude = normal_.Length();
    if (normal_magnitude != 0 && normal_magnitude != 1) {
        normal_.Scale(1.0f / normal_magnitude);
    }
}

void DrawPolygon::ApplyTransform(const gfx::Transform& transform)
{
    for (size_t i = 0; i < points_.size(); i++) {
        transform.TransformPoint(&points_[i]);
    }
}

// TransformToScreenSpace assumes we're moving a layer from its layer space
// into 3D screen space, which for sorting purposes requires the normal to
// be transformed along with the vertices.
void DrawPolygon::TransformToScreenSpace(const gfx::Transform& transform)
{
    ApplyTransform(transform);
    transform.TransformVector(&normal_);
    ConstructNormal();
}

// In the case of TransformToLayerSpace, we assume that we are giving the
// inverse transformation back to the polygon to move it back into layer space
// but we can ignore the costly process of applying the inverse to the normal
// since we know the normal will just reset to its original state.
void DrawPolygon::TransformToLayerSpace(
    const gfx::Transform& inverse_transform)
{
    ApplyTransform(inverse_transform);
    normal_ = gfx::Vector3dF(0.0f, 0.0f, -1.0f);
}

// Split |polygon| based upon |this|, leaving the results in |front| and |back|.
// If |polygon| is not split by |this|, then move it to either |front| or |back|
// depending on its orientation relative to |this|. Sets |is_coplanar| to true
// if |polygon| is actually coplanar with |this| (in which case whether it is
// front facing or back facing is determined by the dot products of normals, and
// document order).
void DrawPolygon::SplitPolygon(std::unique_ptr<DrawPolygon> polygon,
    std::unique_ptr<DrawPolygon>* front,
    std::unique_ptr<DrawPolygon>* back,
    bool* is_coplanar) const
{
    DCHECK_GE(normalized_threshold, std::abs(normal_.LengthSquared() - 1.0f));

    const size_t num_points = polygon->points_.size();
    const auto next = [num_points](size_t i) { return (i + 1) % num_points; };
    const auto prev = [num_points](size_t i) {
        return (i + num_points - 1) % num_points;
    };

    std::vector<float> vertex_distance;
    size_t pos_count = 0;
    size_t neg_count = 0;

    // Compute plane distances for each vertex of polygon.
    vertex_distance.resize(num_points);
    for (size_t i = 0; i < num_points; i++) {
        vertex_distance[i] = SignedPointDistance(polygon->points_[i]);
        if (vertex_distance[i] < -split_threshold) {
            ++neg_count;
        } else if (vertex_distance[i] > split_threshold) {
            ++pos_count;
        } else {
            vertex_distance[i] = 0.0;
        }
    }

    // Handle non-splitting cases.
    if (!pos_count && !neg_count) {
        double dot = gfx::DotProduct(normal_, polygon->normal_);
        if ((dot >= 0.0f && polygon->order_index_ >= order_index_) || (dot <= 0.0f && polygon->order_index_ <= order_index_)) {
            *back = std::move(polygon);
        } else {
            *front = std::move(polygon);
        }
        *is_coplanar = true;
        return;
    }

    *is_coplanar = false;
    if (!neg_count) {
        *front = std::move(polygon);
        return;
    } else if (!pos_count) {
        *back = std::move(polygon);
        return;
    }

    // Handle splitting case.
    size_t front_begin;
    size_t back_begin;
    size_t pre_front_begin;
    size_t pre_back_begin;

    // Find the first vertex that is part of the front split polygon.
    front_begin = std::find_if(vertex_distance.begin(), vertex_distance.end(),
                      [](float val) { return val > 0.0; })
        - vertex_distance.begin();
    while (vertex_distance[pre_front_begin = prev(front_begin)] > 0.0)
        front_begin = pre_front_begin;

    // Find the first vertex that is part of the back split polygon.
    back_begin = std::find_if(vertex_distance.begin(), vertex_distance.end(),
                     [](float val) { return val < 0.0; })
        - vertex_distance.begin();
    while (vertex_distance[pre_back_begin = prev(back_begin)] < 0.0)
        back_begin = pre_back_begin;

    DCHECK(vertex_distance[front_begin] > 0.0);
    DCHECK(vertex_distance[pre_front_begin] <= 0.0);
    DCHECK(vertex_distance[back_begin] < 0.0);
    DCHECK(vertex_distance[pre_back_begin] >= 0.0);

    gfx::Point3F pre_pos_intersection;
    gfx::Point3F pre_neg_intersection;

    // Compute the intersection points. N.B.: If the "pre" vertex is on
    // the thick plane, then the intersection will be at the same point, because
    // we set vertex_distance to 0 in this case.
    PointInterpolate(
        polygon->points_[pre_front_begin], polygon->points_[front_begin],
        -vertex_distance[pre_front_begin] / gfx::DotProduct(normal_, polygon->points_[front_begin] - polygon->points_[pre_front_begin]),
        &pre_pos_intersection);
    PointInterpolate(
        polygon->points_[pre_back_begin], polygon->points_[back_begin],
        -vertex_distance[pre_back_begin] / gfx::DotProduct(normal_, polygon->points_[back_begin] - polygon->points_[pre_back_begin]),
        &pre_neg_intersection);

    // Build the front and back polygons.
    std::vector<gfx::Point3F> out_points;

    out_points.push_back(pre_pos_intersection);
    do {
        out_points.push_back(polygon->points_[front_begin]);
        front_begin = next(front_begin);
    } while (vertex_distance[front_begin] > 0.0);
    out_points.push_back(pre_neg_intersection);
    *front = base::MakeUnique<DrawPolygon>(polygon->original_ref_, out_points,
        polygon->normal_, polygon->order_index_);

    out_points.clear();

    out_points.push_back(pre_neg_intersection);
    do {
        out_points.push_back(polygon->points_[back_begin]);
        back_begin = next(back_begin);
    } while (vertex_distance[back_begin] < 0.0);
    out_points.push_back(pre_pos_intersection);
    *back = base::MakeUnique<DrawPolygon>(polygon->original_ref_, out_points,
        polygon->normal_, polygon->order_index_);

    DCHECK_GE((*front)->points().size(), 3u);
    DCHECK_GE((*back)->points().size(), 3u);
}

// This algorithm takes the first vertex in the polygon and uses that as a
// pivot point to fan out and create quads from the rest of the vertices.
// |offset| starts off as the second vertex, and then |op1| and |op2| indicate
// offset+1 and offset+2 respectively.
// After the first quad is created, the first vertex in the next quad is the
// same as all the rest, the pivot point. The second vertex in the next quad is
// the old |op2|, the last vertex added to the previous quad. This continues
// until all points are exhausted.
// The special case here is where there are only 3 points remaining, in which
// case we use the same values for vertex 3 and 4 to make a degenerate quad
// that represents a triangle.
void DrawPolygon::ToQuads2D(std::vector<gfx::QuadF>* quads) const
{
    if (points_.size() <= 2)
        return;

    gfx::PointF first(points_[0].x(), points_[0].y());
    size_t offset = 1;
    while (offset < points_.size() - 1) {
        size_t op1 = offset + 1;
        size_t op2 = offset + 2;
        if (op2 >= points_.size()) {
            // It's going to be a degenerate triangle.
            op2 = op1;
        }
        quads->push_back(
            gfx::QuadF(first,
                gfx::PointF(points_[offset].x(), points_[offset].y()),
                gfx::PointF(points_[op1].x(), points_[op1].y()),
                gfx::PointF(points_[op2].x(), points_[op2].y())));
        offset = op2;
    }
}

} // namespace cc
